package 热题100;

public class 热题5最长回文子串 {

    public static void main(String[] args) {
        热题5最长回文子串 o = new 热题5最长回文子串();
        System.out.println(o.longestPalindrome("a"));
    }

    /**
     * 给定一个字符串，找到最长回文子串
     * @param s
     * @return
     */
    //中心扩散法
    public String longestPalindrome(String s) {
        char[] ch = s.toCharArray();
        String res = s.substring(0,1);
        //i为中心扩散点
        for (int i = 0; i < ch.length-1; i++) {
            int maxLen = 1;
            //如果是bab这种
            String len1 = help(i,i,s);
            //如果baab这种,所以不能够到最后一位置
            String len2 = help(i,i+1,s);
            if (res.length() < len1.length()){
                res = len1;
            }
            if (res.length() < len2.length()){
                res = len2;
            }
        }
        return res;
    }

    /**
     * 中心扩散，找到各种心的最长回文串
     * @param l 左中心
     * @param r 右中心
     * @param s
     * @return 返回最长回文字串
     */
    public String help(int l,int r,String s){
        char[] ch = s.toCharArray();
        int len = 1;
        String res = s.substring(l,l+1);
        while (l >= 0 && r < ch.length){
            if (ch[l] == ch[r]){
                len = len > (r -l + 1) ? len : (r - l + 1);
                l--;
                r++;
            }else {
                break;
            }
        }
        if (len == 1){
            return res;
        }else {
            return s.substring(l+1,r);
        }
    }

}
